package com.lcm.algorithm.datatest.dp.lis;

import java.util.*;

/**
 * @description: 300. 最长上升子序列
 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
 *
 * 示例:
 *
 * 输入: [10,9,2,5,3,7,101,18]
 * 输出: 4
 * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
 * 说明:
 *
 * 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
 * 你算法的时间复杂度应该为 O(n2) 。
 * 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
 * @author: lcm
 * @create: 2020-04-08 10:25
 **/

public class LengthOfLIS {

    public static void main(String[] args){
        System.out.println(lengthOfLIS(new int[]{1,3,6,7,9,4,10,5,6}));
        System.out.println(lengthOfLIS2(new int[]{1,3,6,7,9,4,10,5,6}));

        TreeSet<Integer> set=new TreeSet<>((o1, o2) -> o2-o1);
        set.add(1);
        set.add(9);
        set.add(10);
        set.add(5);
        System.out.println(set);
    }

    /**
     * 动态规划：每次找出以第i位结尾的数，的最长上升子序列，第i+1个数只需要去和前面的进行比较就行了
     * f(i)=[f(1)...f(i-1)]+1 (vi>vx)
     * O(n^2)
     * 内部的数组让他排序，那么使用二分，可以优化
     * @param nums
     * @return
     */
    public static int lengthOfLIS(int[] nums) {
        if(nums==null||nums.length==0) {
            return 0;
        }
        int[] maxLen=new int[nums.length];
        int result=0;
        for(int i=0;i<nums.length;i++){
            maxLen[i]=1;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    maxLen[i]=Math.max(maxLen[j]+1,maxLen[i]);
                }
            }
            result=Math.max(result,maxLen[i]);
        }
        return result;
    }

    /**
     * 二叉排序树代替数组
     */
    public static int lengthOfLIS2(int[] nums) {
        if(nums==null||nums.length==0) {
            return 0;
        }
        //key存长度，value存index
        TreeSet<Entry> set=new TreeSet<>((o1, o2) -> {
            int key=o2.key-o1.key;
            int value=o1.value-o2.value;
            return key==0?value:key;
        });
        for(int i=0;i<nums.length;i++){
            int key=1;
            for(Entry entry:set){
                if(nums[i]>nums[entry.value]){
                    key=entry.key+1;
                    break;
                }
            }
            set.add(new Entry(key,i));
        }
        return set.first().key;
    }

    static class Entry{
        int key;
        int value;

        public Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}
